// Problem 078: Coin partitions
//
// Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can be separated into piles in exactly seven different ways, so p(5)=7.
// Find the least value of n for which p(n) is divisible by one million.
// ----
// ref:https://math.blogoverflow.com/2014/08/25/playing-with-partitions-eulers-pentagonal-theorem/

package main

import (
	"fmt"
	"math/big"
)

func p078() {
	table078 = make(map[int]*big.Int)
	table078[0] = big.NewInt(1)
	table078[1] = big.NewInt(1)
	million := big.NewInt(1000000)
	zero := big.NewInt(0)
	x := 2
	for {
		v := partition(x)
		if v.Mod(v, million).Cmp(zero) == 0 {
			fmt.Println("Problem 078:", x)
			break
		}
		x++
	}
}

var table078 map[int]*big.Int

func partition(n int) *big.Int {
	if v, ok := table078[n]; ok {
		return v
	}
	result := big.NewInt(0)
	for k := 1; k*(3*k-1)/2 <= n || k*(3*k+1)/2 <= n; k++ {
		if k%2 == 0 {
			if n-k*(3*k-1)/2 >= 0 {
				result.Sub(result, partition(n-k*(3*k-1)/2))
			}
			if n-k*(3*k+1)/2 >= 0 {
				result.Sub(result, partition(n-k*(3*k+1)/2))
			}
		} else {
			if n-k*(3*k-1)/2 >= 0 {
				result.Add(result, partition(n-k*(3*k-1)/2))
			}
			if n-k*(3*k+1)/2 >= 0 {
				result.Add(result, partition(n-k*(3*k+1)/2))
			}
		}
	}
	table078[n] = result
	return result
}
